/*
Date:20210530 16:36PM
key:push数组依次放入栈，出栈数组用一个下标遍历。在大循环内分为两步，
    while栈顶不是当前出栈元素，继续压入栈。
    while栈顶是当前出栈元素，退栈。出栈数组下标+1.
    为真的终止条件是 在出栈循环结束后 观察出栈数组下标是否到了尽头 如果是则为真
    为假的终止条件是 在出栈数组还没到尽头 push数组却已经到了尽头
*/
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) 
    {
        const int n=pushed.size();
        stack<int>s;
        int i=0;
        int j=-1;
        while(1)
        {
            while((i<n)&&(s.empty()||(s.top()!=popped[i])))
            {
                j++;
                if(j==n){return 0;}
                s.push(pushed[j]);   
                   
            } 
            while(!s.empty()&&(s.top()==popped[i]))
            {
                s.pop();
                i++;
            }
            if(i==n){return 1;}
        }
        return 1;
    }
};